Conventional computer systems have a relatively slow storage system (e.g., data stored on hard disks) and a relatively fast memory system (e.g., a standard computer random access memory, or RAM). FIG. 1 is a diagram of a conventional memory system. A cache memory 1 is shown as a fast memory system and a disk 50 is shown as the slow storage system.
In running an application on a system that requires access to data, it is not known what data needs to be accessed. It is desirable that the data that will be accessed soon is stored in the memory system. As shown in FIG. 1, the cache memory 1 has an area 10 that stores data that is currently in use, and an area 20 that contains prefetched data or data that is to be used soon.
Some processing units run an application that requires access to the data in the slow storage system 50 (e.g., some CPUs run a file system or database). The data in the slow storage system 50 is partitioned into pages, which can be cached in the memory system 1 for faster access. In many cases, the application's throughput can be increased by guessing which pages will soon be accessed, and proactively prefetching those pages into the prefetched area 20 of the fast memory system 1.
Storage-centric applications must somehow trade off the benefits of prefetching data that has not recently been accessed but might soon be needed, against the benefits of caching data that has been recently accessed and might soon be needed again. Prior art uses hints provided by applications, but such prior art is application-specific, and does not use the structural information in the data with a dynamically adjustable allocation scheme.